package lq1122;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Main {

	//输入优化模板开始
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
	static int rd() throws IOException {
		st.nextToken();
		return (int) st.nval;
	}
	//输入优化模板结束
	
	//图中点的数量
	static int n;
	//最大整数表示无通路
	static long INF = Long.MAX_VALUE;
    //图——邻接表
    static List<List<int[]>> g = new ArrayList<>();
    public static long[] dijkstra(int start) {
    	//两点间的路径长度
    	long[] dist = new long[n+1];
    	Arrays.fill(dist, INF);
    	//路径点分组
    	boolean[] visited = new boolean[n+1];
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				//dist[o1]大时，返回正数表示o1往后排，升序
				//该优先队列是小顶堆
				return Long.compare(dist[o1],dist[o2]);
			}
        });
        pq.offer(start);
        dist[start] = 0;
        while (!pq.isEmpty()) {
            //取出距离start最近的点
            int u = pq.poll();
            visited[u] = true;
            //遍历u的每条边u-v，如果能通过u使得start到v的距离变得更短，更新start到v的距离dist[v]
            for(int i=0;i<g.get(u).size();i++) {
                int v = g.get(u).get(i)[0];
                int weight = g.get(u).get(i)[1];
                if (!visited[v] && dist[v] > dist[u] + weight) {
                    dist[v] = dist[u] + weight;
                    //将v加入优先队列，下次参与比较距离start最近的点
                    pq.offer(v);
                }
            }
        }      
        return dist;
    }
    
	public static void main(String[] args) throws IOException {
		//建图
		n = rd();
		int m = rd();
		
		//创建点的列表
		//注意：点从1开始编号，但ArrayList需要从0开始依次添加实例
        for (int i = 0; i <= n; i++) {
            g.add(new ArrayList<>());
        }
        
        //添加边
		//get(点id)，add(边(终点，权重))
        while(m>0) {
        	m--;
        	int u = rd();
        	int v = rd();
        	int w = rd();
        	g.get(u).add(new int[]{v,w});
        }     
        
        long[] d = dijkstra(1);
        for(int i=1;i<=n;i++) {
        	if(d[i]<INF)
        		System.out.print(d[i]+" ");
        	else
        		System.out.print("-1 ");
        }
	}
}